home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / ddj0492.zip / GRAPHPRG.ASC < prev    next >
Text File  |  1992-03-10  |  17KB  |  444 lines
  1. _GRAPHICS PROGRAMMING COLUMN_
  2. by Michael Abrash
  3.  
  4.  
  5. [LISTING ONE]
  6.  
  7. ; 386-specific fixed point routines.
  8. ; Tested with TASM 3.0.
  9. ROUNDING_ON     equ     1       ;1 for rounding, 0 for no rounding
  10.                                 ;no rounding is faster, rounding is
  11.                                 ; more accurate
  12. ALIGNMENT       equ     2
  13.         .model small
  14.         .386
  15.         .code
  16. ;=====================================================================
  17. ; Multiplies two fixed-point values together.
  18. ; C near-callable as:
  19. ;       Fixedpoint FixedMul(Fixedpoint M1, Fixedpoint M2);
  20. ;       Fixedpoint FixedDiv(Fixedpoint Dividend, Fixedpoint Divisor);
  21. FMparms struc
  22.         dw      2 dup(?)        ;return address & pushed BP
  23. M1      dd      ?
  24. M2      dd      ?
  25. FMparms ends
  26.         align   ALIGNMENT
  27.         public  _FixedMul
  28. _FixedMul       proc    near
  29.         push    bp
  30.         mov     bp,sp
  31.         mov     eax,[bp+M1]
  32.         imul    dword ptr [bp+M2] ;multiply
  33. if ROUNDING_ON
  34.         add     eax,8000h       ;round by adding 2^(-17)
  35.         adc     edx,0           ;whole part of result is in DX
  36. endif ;ROUNDING_ON
  37.         shr     eax,16          ;put the fractional part in AX
  38.         pop     bp
  39.         ret
  40. _FixedMul       endp
  41. ;=====================================================================
  42. ; Divides one fixed-point value by another.
  43. ; C near-callable as:
  44. ;       Fixedpoint FixedDiv(Fixedpoint Dividend, Fixedpoint Divisor);
  45. FDparms struc
  46.         dw      2 dup(?)        ;return address & pushed BP
  47. Dividend dd     ?
  48. Divisor  dd     ?
  49. FDparms ends
  50.         align   ALIGNMENT
  51.         public  _FixedDiv
  52. _FixedDiv       proc    near
  53.         push    bp
  54.         mov     bp,sp
  55.  
  56. if ROUNDING_ON
  57.         sub     cx,cx           ;assume positive result
  58.         mov     eax,[bp+Dividend]
  59.         and     eax,eax         ;positive dividend?
  60.         jns     FDP1            ;yes
  61.         inc     cx              ;mark it's a negative dividend
  62.         neg     eax             ;make the dividend positive
  63. FDP1:   sub     edx,edx         ;make it a 64-bit dividend, then shift
  64.                                 ; left 16 bits so that result will be in EAX
  65.         rol     eax,16          ;put fractional part of dividend in
  66.                                 ; high word of EAX
  67.         mov     dx,ax           ;put whole part of dividend in DX
  68.         sub     ax,ax           ;clear low word of EAX
  69.         mov     ebx,dword ptr [bp+Divisor]
  70.         and     ebx,ebx         ;positive divisor?
  71.         jns     FDP2            ;yes
  72.         dec     cx              ;mark it's a negative divisor
  73.         neg     ebx             ;make divisor positive
  74. FDP2:   div     ebx             ;divide
  75.         shr     ebx,1           ;divisor/2, minus 1 if the divisor is
  76.         adc     ebx,0           ; even
  77.         dec     ebx
  78.         cmp     ebx,edx         ;set Carry if remainder is at least half as 
  79.         adc     eax,0           ; large as the divisor, then use that to 
  80.                                 ; round up if necessary
  81.         and     cx,cx           ;should the result be made negative?
  82.         jz      FDP3            ;no
  83.         neg     eax             ;yes, negate it
  84. FDP3:
  85. else ;!ROUNDING_ON
  86.         mov     edx,[bp+Dividend]
  87.         sub     eax,eax
  88.         shrd    eax,edx,16      ;position so that result ends up
  89.         sar     edx,16          ; in EAX
  90.         idiv    dword ptr [bp+Divisor]
  91. endif ;ROUNDING_ON
  92.         shld    edx,eax,16      ;whole part of result in DX;
  93.                                 ; fractional part is already in AX
  94.         pop     bp
  95.         ret
  96. _FixedDiv       endp
  97. ;=====================================================================
  98. ; Returns the sine and cosine of an angle.
  99. ; C near-callable as:
  100. ;       void CosSin(TAngle Angle, Fixedpoint *Cos, Fixedpoint *);
  101.  
  102.         align   ALIGNMENT
  103. CosTable label dword
  104.         include costable.inc
  105.  
  106. SCparms struc
  107.         dw      2 dup(?)        ;return address & pushed BP
  108. Angle   dw      ?               ;angle to calculate sine & cosine for
  109. Cos     dw      ?               ;pointer to cos destination
  110. Sin     dw      ?               ;pointer to sin destination
  111. SCparms ends
  112.  
  113.         align   ALIGNMENT
  114.         public _CosSin
  115. _CosSin proc    near
  116.         push    bp              ;preserve stack frame
  117.         mov     bp,sp           ;set up local stack frame
  118.  
  119.         mov     bx,[bp].Angle
  120.         and     bx,bx           ;make sure angle's between 0 and 2*pi
  121.         jns     CheckInRange
  122. MakePos:                        ;less than 0, so make it positive
  123.         add     bx,360*10
  124.         js      MakePos
  125.         jmp     short CheckInRange
  126.  
  127.         align   ALIGNMENT
  128. MakeInRange:                    ;make sure angle is no more than 2*pi
  129.         sub     bx,360*10
  130. CheckInRange:
  131.         cmp     bx,360*10
  132.         jg      MakeInRange
  133.  
  134.         cmp     bx,180*10       ;figure out which quadrant
  135.         ja      BottomHalf      ;quadrant 2 or 3
  136.         cmp     bx,90*10        ;quadrant 0 or 1
  137.         ja      Quadrant1
  138.                                 ;quadrant 0
  139.         shl     bx,2
  140.         mov     eax,CosTable[bx] ;look up sine
  141.         neg     bx              ;sin(Angle) = cos(90-Angle)
  142.         mov     edx,CosTable[bx+90*10*4] ;look up cosine
  143.         jmp     short CSDone
  144.  
  145.         align   ALIGNMENT
  146. Quadrant1:
  147.         neg     bx
  148.         add     bx,180*10       ;convert to angle between 0 and 90
  149.         shl     bx,2
  150.         mov     eax,CosTable[bx] ;look up cosine
  151.         neg     eax             ;negative in this quadrant
  152.         neg     bx              ;sin(Angle) = cos(90-Angle)
  153.         mov     edx,CosTable[bx+90*10*4] ;look up cosine
  154.         jmp     short CSDone
  155.  
  156.         align   ALIGNMENT
  157. BottomHalf:                     ;quadrant 2 or 3
  158.         neg     bx
  159.         add     bx,360*10       ;convert to angle between 0 and 180
  160.         cmp     bx,90*10        ;quadrant 2 or 3
  161.         ja      Quadrant2
  162.                                 ;quadrant 3
  163.         shl     bx,2
  164.         mov     eax,CosTable[bx] ;look up cosine
  165.         neg     bx              ;sin(Angle) = cos(90-Angle)
  166.         mov     edx,CosTable[90*10*4+bx] ;look up sine
  167.         neg     edx             ;negative in this quadrant
  168.         jmp     short CSDone
  169.  
  170.         align   ALIGNMENT
  171. Quadrant2:
  172.         neg     bx
  173.         add     bx,180*10       ;convert to angle between 0 and 90
  174.         shl     bx,2
  175.         mov     eax,CosTable[bx] ;look up cosine
  176.         neg     eax             ;negative in this quadrant
  177.         neg     bx              ;sin(Angle) = cos(90-Angle)
  178.         mov     edx,CosTable[90*10*4+bx] ;look up sine
  179.         neg     edx             ;negative in this quadrant
  180. CSDone:
  181.         mov     bx,[bp].Cos
  182.         mov     [bx],eax
  183.         mov     bx,[bp].Sin
  184.         mov     [bx],edx
  185.  
  186.         pop     bp              ;restore stack frame
  187.         ret
  188. _CosSin endp
  189. ;=====================================================================
  190. ; Matrix multiplies Xform by SourceVec, and stores the result in
  191. ; DestVec. Multiplies a 4x4 matrix times a 4x1 matrix; the result
  192. ; is a 4x1 matrix. Cheats by assuming the W coord is 1 and the
  193. ; bottom row of the matrix is 0 0 0 1, and doesn't bother to set
  194. ; the W coordinate of the destination.
  195. ; C near-callable as:
  196. ;       void XformVec(Xform WorkingXform, Fixedpoint *SourceVec,
  197. ;               Fixedpoint *DestVec);
  198. ;
  199. ; This assembly code is equivalent to this C code:
  200. ;   int i;
  201. ;
  202. ;   for (i=0; i<3; i++)
  203. ;      DestVec[i] = FixedMul(WorkingXform[i][0], SourceVec[0]) +
  204. ;            FixedMul(WorkingXform[i][1], SourceVec[1]) +
  205. ;            FixedMul(WorkingXform[i][2], SourceVec[2]) +
  206. ;            WorkingXform[i][3];   /* no need to multiply by W = 1 */
  207.  
  208. XVparms struc
  209.         dw      2 dup(?)        ;return address & pushed BP
  210. WorkingXform dw ?               ;pointer to transform matrix
  211. SourceVec dw    ?               ;pointer to source vector
  212. DestVec dw      ?               ;pointer to destination vector
  213. XVparms ends
  214.  
  215.         align   ALIGNMENT
  216.         public _XformVec
  217. _XformVec       proc    near
  218.         push    bp              ;preserve stack frame
  219.         mov     bp,sp           ;set up local stack frame
  220.         push    si              ;preserve register variables
  221.         push    di
  222.  
  223.         mov     si,[bp].WorkingXform ;SI points to xform matrix
  224.         mov     bx,[bp].SourceVec    ;BX points to source vector
  225.         mov     di,[bp].DestVec      ;DI points to dest vector
  226.  
  227. soff=0
  228. doff=0
  229.         REPT 3                  ;do once each for dest X, Y, and Z
  230.         mov     eax,[si+soff]   ;column 0 entry on this row
  231.         imul    dword ptr [bx]  ;xform entry times source X entry
  232. if ROUNDING_ON
  233.         add     eax,8000h       ;round by adding 2^(-17)
  234.         adc     edx,0           ;whole part of result is in DX
  235. endif ;ROUNDING_ON
  236.         shrd    eax,edx,16      ;shift the result back to 16.16 form
  237.         mov     ecx,eax         ;set running total
  238.  
  239.         mov     eax,[si+soff+4] ;column 1 entry on this row
  240.         imul    dword ptr [bx+4] ;xform entry times source Y entry
  241. if ROUNDING_ON
  242.         add     eax,8000h       ;round by adding 2^(-17)
  243.         adc     edx,0           ;whole part of result is in DX
  244. endif ;ROUNDING_ON
  245.         shrd    eax,edx,16      ;shift the result back to 16.16 form
  246.         add     ecx,eax         ;running total for this row
  247.  
  248.         mov     eax,[si+soff+8] ;column 2 entry on this row
  249.         imul    dword ptr [bx+8] ;xform entry times source Z entry
  250. if ROUNDING_ON
  251.         add     eax,8000h       ;round by adding 2^(-17)
  252.         adc     edx,0           ;whole part of result is in DX
  253. endif ;ROUNDING_ON
  254.         shrd    eax,edx,16      ;shift the result back to 16.16 form
  255.         add     ecx,eax         ;running total for this row
  256.  
  257.         add     ecx,[si+soff+12] ;add in translation
  258.         mov     [di+doff],ecx   ;save the result in the dest vector
  259. soff=soff+16
  260. doff=doff+4
  261.         ENDM
  262.  
  263.         pop     di              ;restore register variables
  264.         pop     si
  265.         pop     bp              ;restore stack frame
  266.         ret
  267. _XformVec       endp
  268. ;=====================================================================
  269. ; Matrix multiplies SourceXform1 by SourceXform2 and stores the
  270. ; result in DestXform. Multiplies a 4x4 matrix times a 4x4 matrix;
  271. ; the result is a 4x4 matrix. Cheats by assuming the bottom row of
  272. ; each matrix is 0 0 0 1, and doesn't bother to set the bottom row
  273. ; of the destination.
  274. ; C near-callable as:
  275. ;       void ConcatXforms(Xform SourceXform1, Xform SourceXform2,
  276. ;               Xform DestXform)
  277. ;
  278. ; This assembly code is equivalent to this C code:
  279. ;   int i, j;
  280. ;
  281. ;   for (i=0; i<3; i++) {
  282. ;      for (j=0; j<4; j++)
  283. ;         DestXform[i][j] =
  284. ;               FixedMul(SourceXform1[i][0], SourceXform2[0][j]) +
  285. ;               FixedMul(SourceXform1[i][1], SourceXform2[1][j]) +
  286. ;               FixedMul(SourceXform1[i][2], SourceXform2[2][j]) +
  287. ;               SourceXform1[i][3];
  288. ;   }
  289.  
  290. CXparms struc
  291.         dw      2 dup(?)        ;return address & pushed BP
  292. SourceXform1 dw ?               ;pointer to first source xform matrix
  293. SourceXform2 dw ?               ;pointer to second source xform matrix
  294. DestXform    dw ?               ;pointer to destination xform matrix
  295. CXparms ends
  296.  
  297.         align   ALIGNMENT
  298.         public _ConcatXforms
  299. _ConcatXforms   proc    near
  300.         push    bp              ;preserve stack frame
  301.         mov     bp,sp           ;set up local stack frame
  302.         push    si              ;preserve register variables
  303.         push    di
  304.  
  305.         mov     bx,[bp].SourceXform2 ;BX points to xform2 matrix
  306.         mov     si,[bp].SourceXform1 ;SI points to xform1 matrix
  307.         mov     di,[bp].DestXform    ;DI points to dest xform matrix
  308.  
  309. roff=0                          ;row offset
  310.         REPT 3                  ;once for each row
  311. coff=0                          ;column offset
  312.         REPT  4                 ;once for each column
  313.         mov     eax,[si+roff]   ;column 0 entry on this row
  314.         imul    dword ptr [bx+coff] ;times row 0 entry in column
  315. if ROUNDING_ON
  316.         add     eax,8000h       ;round by adding 2^(-17)
  317.         adc     edx,0           ;whole part of result is in DX
  318. endif ;ROUNDING_ON
  319.         shrd    eax,edx,16      ;shift the result back to 16.16 form
  320.         mov     ecx,eax         ;set running total
  321.  
  322.         mov     eax,[si+roff+4] ;column 1 entry on this row
  323.         imul    dword ptr [bx+coff+16] ;times row 1 entry in col
  324. if ROUNDING_ON
  325.         add     eax,8000h       ;round by adding 2^(-17)
  326.         adc     edx,0           ;whole part of result is in DX
  327. endif ;ROUNDING_ON
  328.         shrd    eax,edx,16      ;shift the result back to 16.16 form
  329.         add     ecx,eax         ;running total
  330.  
  331.         mov     eax,[si+roff+8] ;column 2 entry on this row
  332.         imul    dword ptr [bx+coff+32] ;times row 2 entry in col
  333. if ROUNDING_ON
  334.         add     eax,8000h       ;round by adding 2^(-17)
  335.         adc     edx,0           ;whole part of result is in DX
  336. endif ;ROUNDING_ON
  337.         shrd    eax,edx,16      ;shift the result back to 16.16 form
  338.         add     ecx,eax         ;running total
  339.  
  340.         add     ecx,[si+roff+12] ;add in translation
  341.  
  342.         mov     [di+coff+roff],ecx ;save the result in dest matrix
  343. coff=coff+4                     ;point to next col in xform2 & dest
  344.         ENDM
  345.  
  346. roff=roff+16                    ;point to next col in xform2 & dest
  347.         ENDM
  348.  
  349.         pop     di              ;restore register variables
  350.         pop     si
  351.         pop     bp              ;restore stack frame
  352.         ret
  353. _ConcatXforms   endp
  354.         end
  355.  
  356.  
  357.  
  358. [LISTING TWO]
  359.  
  360. /* Object list-related functions. */
  361. #include <stdio.h>
  362. #include "polygon.h"
  363.  
  364. /* Set up the empty object list, with sentinels at both ends to 
  365.   terminate searches */
  366. void InitializeObjectList()
  367. {
  368.    ObjectListStart.NextObject = &ObjectListEnd;
  369.    ObjectListStart.PreviousObject = NULL;
  370.    ObjectListStart.CenterInView.Z = INT_TO_FIXED(-32768);
  371.    ObjectListEnd.NextObject = NULL;
  372.    ObjectListEnd.PreviousObject = &ObjectListStart;
  373.    ObjectListEnd.CenterInView.Z = 0x7FFFFFFFL;
  374.    NumObjects = 0;
  375. }
  376.  
  377. /* Adds an object to the object list, sorted by center Z coord. */
  378. void AddObject(Object *ObjectPtr)
  379. {
  380.    Object *ObjectListPtr = ObjectListStart.NextObject;
  381.  
  382.    /* Find the insertion point. Guaranteed to terminate because of
  383.       the end sentinel */
  384.    while (ObjectPtr->CenterInView.Z > ObjectListPtr->CenterInView.Z) {
  385.       ObjectListPtr = ObjectListPtr->NextObject;
  386.    }
  387.  
  388.    /* Link in the new object */
  389.    ObjectListPtr->PreviousObject->NextObject = ObjectPtr;
  390.    ObjectPtr->NextObject = ObjectListPtr;
  391.    ObjectPtr->PreviousObject = ObjectListPtr->PreviousObject;
  392.    ObjectListPtr->PreviousObject = ObjectPtr;
  393.    NumObjects++;
  394. }
  395.  
  396. /* Resorts the objects in order of ascending center Z coordinate in view space,
  397.    by moving each object in turn to the correct position in the object list. */
  398. void SortObjects()
  399. {
  400.    int i;
  401.    Object *ObjectPtr, *ObjectCmpPtr, *NextObjectPtr;
  402.  
  403.    /* Start checking with the second object */
  404.    ObjectCmpPtr = ObjectListStart.NextObject;
  405.    ObjectPtr = ObjectCmpPtr->NextObject;
  406.    for (i=1; i<NumObjects; i++) {
  407.       /* See if we need to move backward through the list */
  408.       if (ObjectPtr->CenterInView.Z < ObjectCmpPtr->CenterInView.Z) {
  409.          /* Remember where to resume sorting with the next object */
  410.          NextObjectPtr = ObjectPtr->NextObject;
  411.          /* Yes, move backward until we find the proper insertion
  412.             point. Termination guaranteed because of start sentinel */
  413.          do {
  414.             ObjectCmpPtr = ObjectCmpPtr->PreviousObject;
  415.          } while (ObjectPtr->CenterInView.Z <
  416.                ObjectCmpPtr->CenterInView.Z);
  417.  
  418.          /* Now move the object to its new location */
  419.          /* Unlink the object at the old location */
  420.          ObjectPtr->PreviousObject->NextObject =
  421.                ObjectPtr->NextObject;
  422.          ObjectPtr->NextObject->PreviousObject =
  423.                ObjectPtr->PreviousObject;
  424.  
  425.          /* Link in the object at the new location */
  426.          ObjectCmpPtr->NextObject->PreviousObject = ObjectPtr;
  427.          ObjectPtr->PreviousObject = ObjectCmpPtr;
  428.          ObjectPtr->NextObject = ObjectCmpPtr->NextObject;
  429.          ObjectCmpPtr->NextObject = ObjectPtr;
  430.  
  431.          /* Advance to the next object to sort */
  432.          ObjectCmpPtr = NextObjectPtr->PreviousObject;
  433.          ObjectPtr = NextObjectPtr;
  434.       } else {
  435.          /* Advance to the next object to sort */
  436.          ObjectCmpPtr = ObjectPtr;
  437.          ObjectPtr = ObjectPtr->NextObject;
  438.       }
  439.    }
  440. }
  441.  
  442.  
  443.  
  444.